PREREQUISITES: Familiarity in C, C++, or PASCAL.
TOPICS
1. PRELIMINARIES: Introduction. Order Notation. Recursion. Recurrence relations.
2. ABSTRACT DATA TYPES: Stacks. Queues. Lists.
3. LISTS: List operations. List representations. List traversals. Doubly linked lists.
4. TREES: Tree operations. Tree representations. Tree traversals. Threaded trees. Binary trees.
5. DICTIONARIES: Binary search trees. AVL trees. 2-3 trees. B-trees.
Red-black trees. Binomial trees. Splay trees.
6. SETS: Set operations. Set representations. Leftist trees. Heaps.
Min-max heaps. Fibonacci heaps. Union-find. Path compression.
7. HASHING: Chaining. Open addressing. Collision handling.
8. GRAPHS: Graph operations. Graph representations. Basic graph algorithms.
9. MEMORY MANAGEMENT: Garbage collection. Buddy systems.
COURSE REQUIREMENTS: There will be homework assignments, one midterm exam,
a final exam, and programming assignments. The weightings within the semester grade will be:
Homework + Prog. Assignment 25%
Midterm 35%
Final exam 40%
HOMEWORK: Only homework turned in by the due date is guaranteed to be graded. Any special circumstances that cause difficulty in meeting the deadlines should be brought to the attention of the instructor in advance.
CHEATING: With the exception of group assignments, the work (including homework, programming assignments, tests) must be the result of your individual effort. This implies that one student should never have in his/her possession a copy of all or part of another student's homework. It
is your responsibility to protect your work from unauthorized access. Academic dishonesty has no place in a university, in particular, in NTUEE. It wastes our time and yours, and it is unfair to the majority of students. Any form of cheating will automatically result in a failing grade in the
course and will be reported to the Dean's office.